from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0], nums[1])
        l = len(nums)
        return max(self.rob1(nums[0:l - 1]), self.rob1(nums[1:]))

    def rob1(self, nums: List[int]) -> int:
        db = [0] * len(nums)
        db[0] = nums[0]
        db[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            db[i] = max(db[i - 2] + nums[i], db[i - 1])
        return db[-1]


so = Solution()
nums = [1, 2, 3, 1]
print(so.rob(nums))
